package main

import "container/list"

func main() {

}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func addOneRow(root *TreeNode, val int, depth int) *TreeNode {
	if depth == 1 || root == nil {
		return &TreeNode{val, root, nil}
	}
	q := list.New()
	q.PushBack(root)
	level := 1
	for q.Len() > 0 {
		if level == depth-1 {
			break
		}
		size := q.Len()
		for i := 0; i < size; i++ {
			node := q.Remove(q.Front()).(*TreeNode)
			if node.Left != nil {
				q.PushBack(node.Left)
			}
			if node.Right != nil {
				q.PushBack(node.Right)
			}
		}
		level++
	}

	for e := q.Front(); e != nil; e = e.Next() {
		node := e.Value.(*TreeNode)
		cur1 := &TreeNode{val, node.Left, nil}
		cur2 := &TreeNode{val, nil, node.Right}
		node.Left = cur1
		node.Right = cur2
	}
	return root
}
